package code.oldCode.feishuSpecializedTraining.stack_and_queue;

import java.util.*;

/**
 * @author 26029
 * @date 2025/3/10
 * @description
 */
public class MyStackQueue2 {
    // 1047. 删除字符串中的所有相邻重复项
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            Character c = s.charAt(i);
            if (!stack.isEmpty() && stack.peek().equals(c)) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

    // 150. 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if ('0' <= token.charAt(0) && token.charAt(0) <= '9' || token.length() >= 2) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+": {
                        stack.push(num1 + num2);
                        break;
                    }
                    case "-": {
                        stack.push(num1 - num2);
                        break;
                    }
                    case "*": {
                        stack.push(num1 * num2);
                        break;
                    }
                    case "/": {
                        stack.push(num1 / num2);
                        break;
                    }
                }
            }
        }
        return stack.pop();
    }

    // 239. 滑动窗口最大值
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 解法一：优先队列 O(nlogn)，建立维护一个大根堆，遍历nums，如果当前最大值的下标不在k范围内，则poll出去，再取最大值，直到在k内
        int len = nums.length;
        // 定义优先队列，并设定规则，建立大根堆
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o2[0] - o1[0]);
        int[] ans = new int[len - k + 1];
        // 前k个时
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i], i});
        }
        ans[0] = queue.peek()[0];
        // 滑动窗口开始移动时
        for (int i = k; i < len; i++) {
            queue.offer(new int[]{nums[i], i});
            while (queue.peek()[1] <= i - k) {
                queue.poll();
            }
            ans[i - k + 1] = queue.peek()[0];
        }
        return ans;
    }
    public int[] maxSlidingWindow_(int[] nums, int k) {
        // 解法二：单调队列，用一个双端队列便于操作，存放当前窗口的下标，但不保留不可能成为答案的下标
        Deque<Integer> deque = new ArrayDeque<>();
        int len = nums.length;
        int[] ans = new int[len - k + 1];
        for (int i = 0; i < len; i++) {
            // 清除当前不在窗口范围的下标
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.removeFirst();
            }
            // 清除队列比当前数据小（不可能为答案）的数据的下标，这里从Last开始比，因为这个队列虽然存放的是递增的下标，但代表的是递减的num，从队尾比较，符合单调
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            // 当前值的下标加入队列，添加下标只添加在末端上
            deque.addLast(i);
            if (i >= k - 1) {
                ans[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return ans;
    }

    // 347. 前 K 个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        // O(nlogn)做法，优先队列（大根堆）
        int[] ans = new int[k];
        // 构建一个最大堆
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }
        for (Integer key : map.keySet()) {
            int value = map.get(key);
            int[] p = new int[]{value, key};
            priorityQueue.offer(p);
        }
        for (int i = 0; i < k; i++) {
            ans[i] = priorityQueue.poll()[1]; // 测试数据范围内不会出错
        }
        return ans;
    }
    public int[] topKFrequent_(int[] nums, int k) {
        // O(n)做法，桶排序
        int[] ans = new int[k];
        int len = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }
        // 桶排序：准备len(+1)个桶，下标表示数量，内容表示数字
        List<Integer>[] bucket = new List[len + 1];
        for (Integer key : map.keySet()) {
            int value = map.get(key);
            if (bucket[value] == null)
                bucket[value] = new ArrayList<>();
            bucket[value].add(key);
        }
        int pos = 0;
        for (int i = len; i >= 0; i--) {
            if (bucket[i] != null) {
                for (int num : bucket[i]) {
                    ans[pos] = num;
                    pos++;
                }
                if (pos == k)
                    break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        MyStackQueue2 m = new MyStackQueue2();
        m.topKFrequent_(new int[]{1,1,1,2,2,3}, 2);
    }
}
